package com.cg.leetcode;

import org.junit.Test;

/**
 * 538.把二叉搜索树转换为累加树
 *
 * @program: LeetCode->LeetCode_538
 * @author: cg
 * @create: 2022-05-04 11:30
 **/
public class LeetCode_538 {

    @Test
    public void test538() {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(1);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(2);
        root.left.right.right = new TreeNode(3);

        root.right = new TreeNode(6);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);
        root.right.right.right = new TreeNode(8);
        System.out.println(convertBST(root));
    }

    /**
     * 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
     * <p>
     * 提醒一下，二叉搜索树满足下列约束条件：
     * <p>
     * 节点的左子树仅包含键 小于 节点键的节点。
     * 节点的右子树仅包含键 大于 节点键的节点。
     * 左右子树也必须是二叉搜索树。
     * <p>
     * 注意：本题和 1038 相同
     * <p>
     * 示例 1：
     * 输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
     * 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
     * <p>
     * 示例 2：
     * 输入：root = [0,null,1]
     * 输出：[1,null,1]
     * <p>
     * 示例 3：
     * 输入：root = [1,0,2]
     * 输出：[3,3,2]
     * <p>
     * 示例 4：
     * 输入：root = [3,2,4,1]
     * 输出：[7,9,4,10]
     * <p>
     * 提示：
     * 树中的节点数介于 0 和 10^4 之间。
     * 每个节点的值介于 -10^4 和 10^4 之间。
     * 树中的所有值 互不相同 。
     * 给定的树为二叉搜索树。
     *
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }
        // 按右中左顺序遍历，累加即可
        convertBST(root.right);
        sum += root.val;
        root.val = sum;
        convertBST(root.left);
        return root;
    }

    int sum = 0;

}
